https://leetcode.cn/problems/Gu0c2T/description/






class Solution {

private:
    int res = 0;
    int path[110];

public:
    int rob(vector<int>& nums) {

        int n = nums.size();

        memset(path, -1, sizeof(path));

        return dfs(nums, n - 1);

    }

    int dfs(vector<int>& nums, int n)
    {
        if (n < 0)
            return 0;

        if (path[n] != -1)
            return path[n];

        res = max(dfs(nums, n - 1), dfs(nums, n - 2) + nums[n]);

        path[n] = res;

        return res;
    }
};